[go: up one dir, main page]
Scribd
Upload
2 views3 pages

Unit 2 Linear Data Structure

This document covers linear data structures, specifically stacks and queues. It defines stacks as LIFO structures with operations like push, pop, and peek, and discusses their applications such as matching parentheses and recursion. It also explains queues as FIFO structures with operations like enqueue and dequeue, along with their types, including circular queues and priority queues.

Uploaded by

akashiyadav8448
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views3 pages

Unit 2 Linear Data Structure

This document covers linear data structures, specifically stacks and queues. It defines stacks as LIFO structures with operations like push, pop, and peek, and discusses their applications such as matching parentheses and recursion. It also explains queues as FIFO structures with operations like enqueue and dequeue, along with their types, including circular queues and priority queues.

Uploaded by

akashiyadav8448
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

UNIT 2: Linear Data Structure

2.1 Stacks: Stack-definitions; concepts and representation


A stack is a linear data structure that follows the Last In First Out (LIFO) principle. The
element inserted last is the one removed first.

Operations:

- push: Add an element to the top of the stack.

- pop: Remove the top element.

- peek/top: View the top element without removing it.

Representation:

- Array-based: Uses a fixed-size array and a 'top' pointer.

- Linked list-based: Each node contains the data and a pointer to the next node.

2.2 Operations of Stack


Basic operations include:

1. Push: Insert an element at the top.

2. Pop: Remove the top element.

3. Peek: View the top element.

4. isEmpty: Check if the stack is empty.

5. isFull: Check if the stack is full (array-based).

2.3 Applications: Matching Parenthesis; Recursion; Towers of Hanoi


- Matching Parentheses: Stack helps in checking for balanced symbols in expressions.

- Recursion: The call stack stores function calls and local variables.

- Towers of Hanoi: A classic problem solved using recursive algorithms involving stacks.
2.4 Polish Notation: Infix to Postfix Notation; Evaluating Postfix
Expression
- Infix: A + B

- Postfix: AB+

Conversion:

1. Use stack to manage operators based on precedence.

2. Scan the infix expression left to right.

Evaluation of postfix:

- Use a stack, scan the expression:

- If operand: push to stack.

- If operator: pop operands, apply operation, push result.

2.5 Queues: Representation


Queue is a linear data structure that follows First In First Out (FIFO).

Representation:

- Array: Uses front and rear pointers.

- Linked List: Each node has data and a pointer to the next.

2.6 Operations on Queues: Insert; Delete


- Enqueue (Insert): Add an element at the rear.

- Dequeue (Delete): Remove the front element.

- isEmpty: Check if the queue is empty.

- isFull: Check if the queue is full (array-based).

2.7 Circular Queues


A circular queue overcomes the limitation of linear queue (unused space).

Implementation uses modulo operation:

rear = (rear + 1) % size


Full condition: (rear + 1) % size == front

Empty condition: front == -1

2.8 Types of Queue: Deque and Priority Queues


- Deque (Double Ended Queue): Insertion and deletion can be done at both ends.

- Priority Queue: Each element has a priority; element with higher priority is served first.

2.9 Applications of Queue


- CPU scheduling

- Disk scheduling

- Printer queue management

- Breadth First Search (BFS)

- Call center systems

- Web server request management

You might also like