Data structures and algorithms: stacks and queues

1. Introduction

This is the third installment in our data Structures and Algorithms series on stacks and queues.

2. The stack

A stack is a special linear table that allows operations on only one end (called the top of the stack), as shown here:

33 is the top of the stack and 11 is the bottom of the stack (although we generally don’t talk about the bottom of the stack)

2.1 Common Operations

Push: To push into a stackaddThe operation on the element is calledPush (push), as shown in the figure:

Out of the stack: From the stackremoveThe operation on the element is calledOut of stack (POP), as shown in the figure:

Since only the top element can be removed from the stack, ejecting the stack is also called ejecting the top element

Last In First Out (LIFO)

2.2 Implementation of stack structure

2.2.1 Interface design

If you want to design a stack structure, you usually implement the following basic interfaces:

@protocol StackProtocol <NSObject>

@required

// the number of elements
- (NSUInteger)size;

/// Is empty
- (BOOL)isEmpty;

/ / / into the stack
- (void)push:(id)element;

/ / / out of the stack
- (id)pop;

/// get the top element of the stack
- (id)top;

/ / / empty
- (void)clear;

@end
Copy the code

2.2.2 Specific implementation

Create the Stack class as follows:

Stack.h:StackClass followStackProtocolagreement

@interface Stack : NSObject <StackProtocol>

@end
Copy the code

Stack.m: Since only the top element of the stack is changed, the dynamic array is chosen here.NSMutableArray), the time complexity isO(1)

@interface Stack (a)

@property (nonatomic, strong) NSMutableArray *list;

@end

@implementation Stack

- (instancetype)init
{
    if (self = [super init]) {
        self.list = [[NSMutableArray alloc] init];
    }
    return self;
}

#pragma mark - StackProtocol

// the number of elements
- (NSUInteger)size
{
    return _list.count;
}

/// Is empty
- (BOOL)isEmpty
{
    return _list.count == 0;
}

/ / / into the stack
- (void)push:(id)element
{
    if(element) { [_list addObject:element]; }}/ / / out of the stack
- (id)pop
{
    if (_list.count > 0) {
        id lastObj = _list.lastObject;
        [_list removeLastObject];
        return lastObj;
    }
    return nil;
}

/// get the top element of the stack
- (id)top
{
    if (_list.count > 0) {
        return _list.lastObject;
    }
    return nil;
}

/ / / empty
- (void)clear
{
    [_list removeAllObjects];
}

@end
Copy the code

2.2.3 Code test

Add the test code to main.m as follows:

#import <Foundation/Foundation.h>
#import "Stack.h"

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        Stack *stack = [[Stack alloc] init];
        [stack push:@11];
        [stack push:@22];
        [stack push:@33];
        [stack push:@44];
        
        while(! [stack isEmpty]) {
            NSLog(@"pop item: %lld", ((NSNumber *)[stackpop]).longLongValue); }}return 0;
}
Copy the code

The output after the run is:

Obviously passed the test!

2.3 Application of stack

Stack application scenarios are familiar to us, such as:

Undo and Redo functions of the software
Browser forward and backward functions

2.4 Exercise: Valid parentheses

Let’s practice with a simple Leetcode algorithm: 20- valid brackets

2.4.1 Problem Description (From LeetCode)

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:
- An open parenthesis must be closed with a close parenthesis of the same type.
- The left parentheses must be closed in the correct order.
Example:

Input: s = "() [] {}" output: true input: s = "([]" output: false input: s = "{[]}" output: true input: s = "{} [])" output: falseCopy the code

2.4.2 Solution ideas

Considering the use of stack to solve the problem, it is necessary to think about the operation of the stack, the idea is as follows:

String character by character traversal;
If the left character ((,[,{), then push;
If it is the right character (),],}), check whether the stack is empty:
- If the stack is empty, indicatingParentheses is invalidDirectly,return false
- If the stack is not empty, the top character of the stack is popped, matching the right character
  - If the result matches, proceed to scan the next character
  - If the result does not match, it indicatesParentheses is invalidDirectly,return false
After all characters are scanned, if:
- If the stack is empty, indicatingParentheses effectively.return true;
- The stack is not emptyParentheses is invalid.return false;

2.4.3 Specific implementation

The specific implementation code is as follows:

/** Valid parentheses: leetcode_20 (https://leetcode-cn.com/problems/valid-parentheses/) */
+ (BOOL)isValidBrackets:(NSString *)brackets
{
    if(! brackets || ! brackets.length) {return NO;
    }
    Stack *stack = [[Stack alloc] init];
    NSDictionary<NSString *, NSString *> *dict = @{
        @"(" : @")"The @"[" : @"]"The @"{" : @"}"}; NSArray *allKeys = dict.allKeys; NSUInteger length = brackets.length; NSRange range;for (int i = 0; i < length; i += range.length) {
        range = [brackets rangeOfComposedCharacterSequenceAtIndex:i];
        NSString *sub = [brackets substringWithRange:range];
        if ([allKeys containsObject:sub]) {/ / left parenthesis
            [stack push:sub];
        } else {/ / right parenthesis
            if (stack.isEmpty || ! [sub isEqualToString:dict[stack.pop]]) {
                returnNO; }}}return stack.isEmpty;
}
Copy the code

2.4.4 Code test

The test code is as follows:

#import "StackDemo.h"

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        NSArray<NSString *> *expArray = @[@"[the] {} ()"The @"([]"The @"{[]}"The @"{} [])"];
        for (NSString *exp in expArray) {
            NSLog(@"%@ isValid: %@".exp, [StackDemo isValidBrackets:exp]? @"true" : @"false"); }}return 0;
}
Copy the code

The results are shown below:

Test passed!

3. The queue

A queue is a special linear table that can operate on both ends, as shown in the figure below:

3.1 Common Operations

The two ends of a queue are rear and front. Common operations are as follows:

To go into a queueaddThe operation on the element is calledThe team(i.e.enqueue), as shown in the figure:

The end of the team is called rear.

Out: From a queueremoveThe operation on the element is calledOut of the team(i.e.dequeue), as shown in the figure:

The end of the line is called the front.

First In First Out (FIFO)

3.2 Implementation of queue structure

3.2.1 Interface Design

The generic interface of queues is similar to that of stacks, for example:

@protocol QueueProtocol <NSObject>

@required

// the number of elements
- (NSUInteger)size;

/// Is empty
- (BOOL)isEmpty;

/ / / team
- (void)enqueue:(id)element;

/ / / out of the team
- (id)dequeue;

/// get the header element of the queue
- (id)front;

/ / / empty
- (void)clear;

@end
Copy the code

3.2.2 Specific implementation

Create Queue class, the specific code implementation is as follows:

Queue.h:QueueClass followQueueProtocolagreement

@interface Queue : NSObject <QueueProtocol>

@end
Copy the code

Queue.m: Is preferred because the queue is a two-end operation (head and tail)Double linkedListIn order to achieve the time complexity of queue operationsO(1)Level.

For bidirectional linked lists, go to Data Structures and Algorithms: Linked Lists, or visit the blogger’s Github

@interface Queue (a)

@property (nonatomic, strong) DoublyLinkedList *list;

@end

@implementation Queue

- (instancetype)init
{
    if (self = [super init]) {
        self.list = [[DoublyLinkedList alloc] init];
    }
    return self;
}

#pragma mark - QueueProtocol

// the number of elements
- (NSUInteger)size
{
    return [_list size];
}

/// Is empty
- (BOOL)isEmpty
{
    return [_list isEmpty];
}

/ / / team
- (void)enqueue:(id)element
{
    [_list add:element];
}

/ / / out of the team
- (id)dequeue
{
    return [_list remove:0];
}

/// get the header element of the queue
- (id)front
{
    return [_list get:0];
}

/ / / empty
- (void)clear
{
    [_list clear];
}

@end
Copy the code

3.2.3 Code testing

Add the test code to main.m as follows:

// main.m
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        [QueueDemo testQueue];
    }
    return 0;
}

// QueueDemo.m
+ (void)testQueue
{
    Queue *queue = [[Queue alloc] init];
    [queue enqueue:@11];
    [queue enqueue:@22];
    [queue enqueue:@33];
    [queue enqueue:@44];
    while(! [queue isEmpty]) {
        NSLog(@"dequeue item: %@"[queuedequeue]); }}Copy the code

The output after the run is:

Obviously passed the test!

3.3 Queue Application

Queues are widely used in daily life. Anything that involves queuing is basically queuing, such as:

Line up for vaccines
Waiting in line for tickets at the station

3.4 Dual-ended Queue

Dual-end queue: a queue that can enter and exit a queue at both ends. It’s a deque (short for double Ended Queue).

Compared with common queues, only the following interfaces need to be added to implement dual-end queues:

@protocol DequeProtocol <QueueProtocol>

@required

/// join from the back of the line
- (void)enqueueRear:(id)element;

/// join the team from the head
- (void)enqueueFront:(id)element;

/// from the end of the line
- (id)dequeueRear;

/// get out of the queue
- (id)dequeueFront;

/// get the last element of the queue
- (id)rear;
Copy the code

The implementation of these interfaces is as follows:

/// get out of the queue
- (id)dequeueFront
{
    return [_list remove:0];
}

/// from the end of the line
- (id)dequeueRear
{
    return [_list remove:(_list.size - 1)];
}

/// join the team from the head
- (void)enqueueFront:(id)element
{
    [_list add:element atIndex:0];
}

/// join from the back of the line
- (void)enqueueRear:(id)element
{
    [_list add:element];
}

/// get the last element of the queue
- (id)rear
{
    return [_list get:(_list.size - 1)];
}
Copy the code

3.4.1 Test queue

The test code for the double-ended queue is as follows:

/// Test a double-endian queue
+ (void)testDeque
{
    Deque *queue = [[Deque alloc] init];
    [queue enqueueFront:@11];
    [queue enqueueFront:@22];
    [queue enqueueFront:@33];   // Tail [11, 22, 33] head
    [queue enqueueRear:@44];
    [queue enqueueRear:@55];
    [queue enqueueRear:@66];    // Tail [66, 55, 44, 11, 22, 33
    [queue dequeueFront];       // Tail [66, 55, 44, 11, 22] head
    [queue dequeueRear];        // Tail [55, 44, 11, 22] head
    while(! [queue isEmpty]) {
        NSLog(@"dequeue item: %@"[queuedequeueFront]); }}Copy the code

And test results:

Obviously passed the test!

4 summarizes

That’s it for stacks and queues. Now to sum up:

The stackandThe queueAre special linear tables (the bottom layer can be implemented by arrays or linked lists)
The stackThe feature isLast in first Out (LIFO).The queueThe feature isFirst in, first out (FIFO)

Because these two data structures are similar and different, the blogger places them in the same space. In accordance with the convention, the next one or two algorithms as an exercise.

4.1 Exercise 1: Implementing stacks with queues

Implementing a stack with a queue is LeetCode number 225.

You can implement a stack with only two queues and support all four operations of a normal stack: push, pop, get top, isEmpty

4.1.1 Implementation Idea

In order to satisfy the nature of the stack (LIFO), when a stack is implemented using queues, the last element to be pushed must be the element at the head of the queue.

Queue1 is the primary queue, which is used to store pushed elements. Queue2 is the secondary queue, which is used to store pushed elements. For each stack operation, ensure that the secondary queue is empty (with 0 elements). The specific implementation scheme is as follows:

When pushing (if pushing element is a) :
- Join element A in the teamqueue2At this time,queue2There is only one element a in.
- thequeue1All of the elements of the team in turn out, merge into the teamqueue2
- exchangequeue1,queue2

After the preceding operations are complete, Queue2 is still an empty queue. Queue1 corresponds to the top and bottom of the stack respectively

When out of the stack: call directlyqueue1Out of the team method can

4.1.2 Concrete implementation

The specific code is as follows:

@implementation StackByQueue {
    Queue *_queue1;
    Queue *_queue2;
}

- (instancetype)init
{
    self = [super init];
    if (self) {
        _queue1 = [[Queue alloc] init];
        _queue2 = [[Queue alloc] init];
    }
    return self;
}

#pragma mark - StackProtocol

- (void)clear
{
    [_queue1 clear];
}

- (BOOL)isEmpty
{
    return [_queue1 isEmpty];
}

/ / / out of the stack
- (id)pop
{
    return [_queue1 dequeue];
}

/ / / into the stack
- (void)push:(id)element
{
    [_queue2 enqueue:element];
    while(! [_queue1 isEmpty]) { id element = [_queue1 dequeue]; [_queue2 enqueue:element]; } Queue *temp = _queue1; _queue1 = _queue2; _queue2 = temp; } - (NSUInteger)size {return [_queue1 size];
}

/// get the top element of the stack
- (id)top
{
    return [_queue1 front];
}

@end
Copy the code

4.1.3 Code test

Add the following test code:

+ (void)testStackByQueue
{
    StackByQueue *stack = [[StackByQueue alloc] init];
    [stack push:@11];
    [stack push:@22];
    [stack push:@33];
    [stack push:@44];
    while(! [stack isEmpty]) {
        NSLog(@"pop item: %lld", ((NSNumber *)[stackpop]).longLongValue); }}Copy the code

The test results are as follows:

Obviously passed the test!

4.1.4 Using a queue

What if you use a queue?

Whether you implement a stack with one queue or two queues, the idea is to ensure that the order of the elements from the top of the stack to the bottom of the stack is the same as the order of the elements from the head to the end of the main queue (the queue where the data is stored). In this way, out of the stack is out of the queue. Therefore, the key is the push operation!

When a queue (labeled queue) is used, it is pushed as follows (if the pushed element is a) :

First record the number of elements before the stack, denoted as n (n >= 0);
A team
Then put thequeueThe first n elements of “out + in”

The implementation of pushing is as follows:

/ / / into the stack
- (void)push:(id)element
{
    NSUInteger preSize = [_queue size];
    [_queue enqueue:element];
    for (NSUInteger i = 0; i < preSize; i++) { id element = [_queue dequeue]; [_queue enqueue:element]; }}Copy the code

Other implementations will not be described here, the code has been uploaded to Github (link at the end of this article) ~

4.2 Exercise 2: Implementing queues with stacks

Implementing a stack with a queue is LeetCode problem 232.

You can implement a queue with only two stacks and support all four operations on a normal queue: enqueue, dequeue, front, isEmpty.

4.2.1 Implementation Idea

Since the stack is LIFO, a single dump is enough to ensure positive order (the order of the elements in the queue), so we use inStack and outStack to name the two stacks. The main idea is as follows:

Enqueue (if element A) : pushes element A toinStack
When getting out, follow:
- ifoutStackIs empty, theinStackAll the elements in theoutStack.outStackPops the top of the stack element
- ifoutStackDon’t empty,outStackPops the top of the stack element

4.2.2 Specific implementation

The specific code for implementing queues with stacks is as follows:

@implementation QueueByStack
{
    Stack *_inStack;
    Stack *_outStack;
}

- (instancetype)init
{
    self = [super init];
    if (self) {
        _inStack = [[Stack alloc] init];
        _outStack = [[Stack alloc] init];
    }
    return self;
}

#pragma mark - QueueProtocol

/// Empty the elements
- (void)clear
{
    [_inStack clear];
    [_outStack clear];
}

/ / / out of the team
- (id)dequeue
{
    [self checkOutStack];
    return [_outStack pop];
}

/ / / team
- (void)enqueue:(id)element
{
    [_inStack push:element];
}

/// get the team head
- (id)front
{
    [self checkOutStack];
    return [_outStack top];
}

/// Is empty
- (BOOL)isEmpty
{
    return [_inStack isEmpty] && [_outStack isEmpty];
}

- (NSUInteger)size
{
    return [_inStack size] + [_outStack size];
}

#pragma mark - Private

/// If outStack is empty, dump the inStack data into outStack
- (void)checkOutStack
{
    if ([_outStack isEmpty]) {
        while(! [_inStack isEmpty]) { [_outStack push:[_inStack pop]]; }}}Copy the code

4.2.3 Code testing

Add the following test code:

+ (void)testQueueByStack
{
    QueueByStack *queue = [[QueueByStack alloc] init];
    [queue enqueue:@11];
    [queue enqueue:@22];
    [queue enqueue:@33];
    [queue enqueue:@44];
    while(! [queue isEmpty]) {
        NSLog(@"dequeue item: %@"[queuedequeue]); }}Copy the code

The test results are as follows:

Obviously passed the test!

5. Links

Data structures and algorithms: linked lists
leetcode

6. Supplementary notes

Original link, reproduced please indicate the source!
All of the code has been uploaded to Github for those interested.

Data structures and algorithms: stacks and queues

1. Introduction

2. The stack

2.1 Common Operations

2.2 Implementation of stack structure

2.2.1 Interface design

2.2.2 Specific implementation

2.2.3 Code test

2.3 Application of stack

2.4 Exercise: Valid parentheses

2.4.1 Problem Description (From LeetCode)

2.4.2 Solution ideas

2.4.3 Specific implementation

2.4.4 Code test

3. The queue

3.1 Common Operations

3.2 Implementation of queue structure

3.2.1 Interface Design

3.2.2 Specific implementation

3.2.3 Code testing

3.3 Queue Application

3.4 Dual-ended Queue

3.4.1 Test queue

4 summarizes

4.1 Exercise 1: Implementing stacks with queues

4.1.1 Implementation Idea

4.1.2 Concrete implementation

4.1.3 Code test

4.1.4 Using a queue

4.2 Exercise 2: Implementing queues with stacks

4.2.1 Implementation Idea

4.2.2 Specific implementation

4.2.3 Code testing

5. Links

6. Supplementary notes

Related Posts

Introduction and application of Xcode Text Macros

Some understanding of the iOS Responder Chain

Analysis of iOS interface performance optimization