Lecture Data Structures & Algorithms: Chapter 6

Lecture Data Structures & Algorithms: Chapter 6 - Stacks & Queues (Use Array to implement Stacks & Queues, Use Linked list to implement Stacks & Queues) presented Stacks, Queues and other content. Invite you to read the lecture.
Nội dung trích xuất từ tài liệu:
Lecture Data Structures & Algorithms: Chapter 6 DONG NAI UNIVERSITY OF TECHNOLOGYData Structures & Algorithms 1 DONG NAI UNIVERSITY OF TECHNOLOGY Stacks & Queues Use Array to implement Stacks & QueuesUse Linked list to implement Stacks & Queue 2 DONG NAI UNIVERSITY OF TECHNOLOGY Stacks• LIFO (last in first out) 3 DONG NAI UNIVERSITY OF TECHNOLOGYManaging Top element 4 DONG NAI UNIVERSITY OF TECHNOLOGYBasic operations: Initialize CreateNode Push Pop 5 DONG NAI UNIVERSITY OF TECHNOLOGY typedef struct Node { int data; Node *pLink;Initialize }; typedef struct Node *STACK; void initialize(STACK &stack) { stack=NULL; } 6 DONG NAI UNIVERSITY OF TECHNOLOGY Node *createNode(int d) { Node *pNode=new Node; pNode->data=d;CreateNode pNode->pLink=NULL; } 113 pNode pLink NULL 7 DONG NAI UNIVERSITY OF TECHNOLOGYPush void push(STACK &stack,int d) { Stac 114 k Node *pNode=createNode(d); pLink pNode 114 if(stack==NULL) pLink { stack=pNode; NULL } Stac k else 113 113 { pLink pLink pNode->pLink=stack; stack=pNode; } NULL NULL} 8 DONG NAI UNIVERSITY OF TECHNOLOGYPop Stac int pop(STACK k 114 114 &stack) 114 pDel {pLink pLink pLink int d=stack->data; Stac NULL Node *pDel=stack; Stac NULL k k stack=stack- 113 113 113 >pLink;pLink pLink pLink pDel- >pLink=NULL;NULL NULL NULL delete pDel; return d; } 9 DONG NAI UNIVERSITY OF TECHNOLOGYvoid main(){ STACK stack; initialize(stack); push(stack,5); push(stack,7); push(stack,1); cout DONG NAI UNIVERSITY OF TECHNOLOGY Queuesl FIFO (first in first out) 11 DONG NAI UNIVERSITY OF TECHNOLOGYQueues 12 DONG NAI UNIVERSITY OF TECHNOLOGYBasic operations: Initialize CreateNode Insert Get 13 DONG NAI UNIVERSITY OF TECHNOLOGY typedef struct Node { int data; Node *pLink; }; typedef struct QUEUEInitialize { Node *pFront; Node *pRear; }; void initialize(QUEUE &queue) { queue.pFront=NULL; queue.pRear=NULL; } 14 DONG NAI UNIVERSITY OF TECHNOLOGY Node *CreateNode(int d) { Node *pNode=new Node; if(pNode==NULL)CreateNode { coutpLink=NULL; } 15 DONG NAI UNIVERSITY OF TECHNOLOGY void Insert(QUEUE &queue,int d) { Node *pNode=CreateNode(d); if(queue.pFront==NULL) {Insert queue.pFront=queue.pRear=pNode; } else { queue.pRear->pLink=pNode; queue.pRear=pNode; } } 16 DONG NAI UNIVERSITY OF TECHNOLOGY int Get(QUEUE &queue) { int d=queue.pFront->data; Node *pDel=queue.pFront;Get queue.pFront=queue.pFront->pLink; pDel->pLink=NULL; delete pDel; return d; } ...