Bài giảng Data Structures & Algorithms - Chương 6: Stacks & Queues

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 05/05/2014 ‹#› Data Structures & Algorithms Stacks & Queues Use Array to implement Stacks & Queues Use Linked list to implement Stacks & Queues LIFO (last in first out) Stacks Managing Top element Basic operations: Initialize CreateNode Push Pop Initialize typedef struct Node { 	int data; 	Node *pLink; }; typedef struct Node *STACK; void initialize(STACK &stack) { 	stack=NULL;	 } CreateNode Node *createNode(int d) { 	Node *pNode=new Node; 	pNode->data=d; 	pNode->pLink=NULL; } NULL 113 pLink pNode Push void push(STACK &stack,int d) { 	Node *pNode=createNode(d); 	if(stack==NULL) 	{ 	stack=pNode;	 	} 	else 	{ 	pNode->pLink=stack; 	stack=pNode;	 	}	 } 113 pLink 114 pLink Stack 113 pLink 114 pLink Stack NULL pNode NULL NULL Pop int pop(STACK &stack) { int d=stack->data; Node *pDel=stack; stack=stack->pLink; pDel->pLink=NULL; delete pDel; return d; } 113 pLink 114 pLink Stack NULL 113 pLink Stack 113 pLink 114 pLink Stack NULL NULL NULL pDel 114 pLink NULL void main() { 	STACK stack; 	initialize(stack); 	push(stack,5); 	push(stack,7); 	push(stack,1); 	coutdata=d; 	pNode->pLink=NULL; } Insert void Insert(QUEUE &queue,int d) { 	Node *pNode=CreateNode(d); 	if(queue.pFront==NULL) 	{ 	queue.pFront=queue.pRear=pNode; 	} 	else 	{ 	queue.pRear->pLink=pNode; 	queue.pRear=pNode; 	} } int Get(QUEUE &queue) { 	int d=queue.pFront->data; 	Node *pDel=queue.pFront; 	queue.pFront=queue.pFront->pLink; 	pDel->pLink=NULL; 	delete pDel; 	return d; } Get END