链表与下压堆栈

链表

节点记录

struct Node
{
  int item;
  Node *next;
};

构造链表

为每个元素创造节点

Node *first=new Node;
Node *second=new Node;
Node *third=new Node;

将每个结点的item域设为所需的值

first->item="to";
second->item="be";
third->item="or"

设置next域来构造链表

first->next=second;
second->next=third;

下压堆栈(LIFO)

在表头插入节点

void push(int item)
{
	Node *newNode=new Node;
	newNode->item=item;
	newNode->next=first;
	first=newNode;
	N++;
}

从表头删除节点

int pop()
{
	int item=first->item;
	first=first->next;
	N--;
	return item;
}

遍历链表

for(Node *x=first;x!=NULL;x=x->next)
{
    //处理x->item
}

完整实现

#include<bits/stdc++.h>
using namespace std;

int N;

struct Node
{
  int item;
  Node *next;
};

Node *first = NULL;

void push(int item)
{
	Node *newNode=new Node;
	newNode->item=item;
	newNode->next=first;
	first=newNode;
	N++;
}

int pop()
{
	int item=first->item;
	first=first->next;
	N--;
	return item;
}

int main()
{
	push(1);push(3);push(2);push(4);
	for(Node *x=first;x!=NULL;x=x->next)
	{
		cout<<pop();
	}
	return 0;
}