2017-11-02 21:49:15 weixin_40458609 阅读数 292
  • 数据结构基础系列(3):栈和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

1.栈的定义是啥?

答:栈是限定只在表尾进行插入和删除操作的线性表。

 

2、理解栈的定义的注意点?

答:

(1)首先它是一个线性表,栈元素具有线性关系,即前驱后继关系。

(2)它的特殊之处在于限制了这个线性表的插入和删除位置,它始终只在栈顶进行。

(3)栈的插入操作,叫做进栈。

(4)栈的删除操作,叫做出栈。

 

3、栈和普通线性表的不同点?

答:

栈是特殊的线性表,是只允许在一端进行插入和删除操作的线性表。允许插入和删除的叫栈顶,反之则是栈底。栈的特点是:后进先出。

普通的线性表可以在头节点出进行插入删除操作。也能在线性表末端进行插入删除。

 

4、堆栈有哪些实际的应用?

答:

1)用于符号匹配;

2)用于计算代数式(也可以用二叉树解决);

3)构造表达式(也可以用二叉树解决);

4)用于函数调用

 

5、栈的基本运算有哪些?

答:

1) initstack(s),构造一个空栈;

2) stackempty(s),判栈空;

3) stackfull(s),判栈满;

4) push(s,x),进栈;

5) pop (s),退栈;

6) stacktop(s),取栈顶元素。

 

6、两栈共享空间能不能扩展空间?

答:

两个栈如果增加元素,就是两端点向中间延伸。并且事实上,使用这样的数据结构,通常都是当两个栈的空间需求有相反关系时,也就是一个栈增长时另一个栈在缩短的情况

 

7、链栈的空间利用率和顺序栈的比较?

答:

链栈能够克服用数组实现的顺序栈空间利用率不高的特点,但是需要为每个栈元素分配额外的指针空间用来存放指针域。

8、循环队列和两栈共享空间的区别?

答:

两者都是为了提高空间利用率,并且循环队列是对队列的改进,两栈是两个栈共享一块内存空间。

 

9、栈的“上溢”和“下溢”怎么理解?

答:

当栈满时,做进栈运算必定产生空间溢出,称“上溢”。 当栈空时,做退栈运算必定产生空间溢出,称“下溢”。上溢是一种错误应设法避免,下溢常用作程序控制转移的条件。

 

10、什么是队列的链式存储结构?

答:

其实就是线性表的单链表,只不过只能尾进头出而已,简称为链队列,为了操作上的方便,我们将对头指针指向链队列的头结点,而队尾指针指向终端节点,空队列时,front和rear都指向头结点。

 

2017-04-23 15:33:46 kaifa1321 阅读数 330
  • 数据结构基础系列(3):栈和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

概述

栈和队列都是通过动态集合来存储数据,在栈和队列中添加和删除数据都是预先设定的,在栈(Stack)中,被删除的元素是最近添加的元素,所以栈的实现方式是后进先出(Last-in, First-out);在队列中,被删除的元素是最开始添加的的元素,也就是在动态集合中存放时间最长的那个元素,所以队列的实现方式是先进先出(First-in,First-out)。

在栈的数据结构中,添加元素的操作被称之为入栈(PUSH),删除元素的操作被称之为出栈,也可以称为弹出(POP)。如果栈中不存在任何一个元素,那么这个栈被称为空栈。

这里写图片描述

栈的代码实现

package structdemo;

/**
 * 栈
 */
public class Stack<E> {

    /**
     * 初始大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    private Object[] elementData;

    public Stack() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    private int size;

    public int getSize() {
        return size;
    }

    /**
     * 判断元素是否为空
     */
    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    /**
     * 压入
     * 
     * @param e
     */
    public void push(E e) {
        ensureCapacity();
        elementData[size] = e;
        size++;
    }

    /**
     * 数组扩容
     */
    private void ensureCapacity() {
        int oldCapacity = elementData.length;
        if (size == oldCapacity) {
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            Object[] newTable = new Object[newCapacity];
            System.arraycopy(elementData, 0, newTable, 0, size);
            elementData = newTable;
        }
    }

    /**
     * 出栈
     * 
     * @return
     */
    public E pop() {
        if (size == 0) {
            return null;
        }
        E e = (E) elementData[size - 1];
        size--;
        return e;
    }

}

队列

在队列中,添加元素的操作被称之为入队(enqueue),而删除元素的操作被称之为出队(dequeue)。在队列中,会有队头(head)和队尾(tail)。当一个元素入队时,该元素就被放入到队尾的位置,而出队的元素就是队头的元素。

这里写图片描述

队列的代码实现

package structdemo;

/**
 * 队列
 * 
 * @author zhangke
 *
 * @param <E>
 */
public class Queue<E> {

    /**
     * 初始大小
     */
    private static final int DEFAULT_CAPACITY = 10;

    private Object[] elementData;

    /**
     * 队头和队尾
     */
    private E head, tail;

    public Queue() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    private int size;

    public int getSize() {
        return size;
    }

    /**
     * 判断元素是否为空
     */
    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    /**
     * 入队
     * 
     * @param e
     */
    public void enqueue(E e) {
        ensureCapacity();
        elementData[size] = e;
        size++;
    }

    /**
     * 数组扩容
     */
    private void ensureCapacity() {
        int oldCapacity = elementData.length;
        if (size == oldCapacity) {
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            Object[] newTable = new Object[newCapacity];
            System.arraycopy(elementData, 0, newTable, 0, size);
            elementData = newTable;
        }
    }

    /**
     * 弹出
     * 
     * @return
     */
    public E dequeue() {
        if (size == 0) {
            return null;
        }
        E e = (E) elementData[0];
        System.arraycopy(elementData, 1, elementData, 0, size - 1);
        elementData[--size] = null;
        return e;
    }

    /**
     * 队头
     * 
     * @return
     */
    public E getHead() {
        if (size == 0) {
            return null;
        }
        return (E) elementData[0];
    }

    /**
     * 队尾
     * 
     * @return
     */
    public E getTail() {
        if (size == 0) {
            return null;
        }
        return (E) elementData[size - 1];
    }

}
2019-04-16 10:45:20 Luqiang_Shi 阅读数 215
  • 数据结构基础系列(3):栈和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚


栈、队列、堆是基础的数据结构类型,其中栈是后进先出的数据结构;队列是先进先出的数据结构;堆通常可以被看成一棵树,又可以被分为最小堆和最大堆,最小堆是指堆中某个节点的元素总不大于其父节点的值;最大堆是指堆中某个元素总不小于其父节点的值。

一、栈的python实现

1.1、栈的列表实现方法

列表(list)是python中经常用到的基础数据结构,我们可以使用列表来模拟栈,实现入栈,出栈等效果。

stack = []
#入栈
stack.append(1)
print(stack)
stack.append(2)
print(stack)
stack.append(5)
print(stack)
#查看栈顶元素
top = stack[-1]
print('栈顶元素为:',top)
#出栈
stack.pop()
print(stack)
#判断栈是否为空
if stack:
    print('Not Empty')
else:
    print('Empty')

1.2、用双向队列模拟栈

python的内置模块collections中包含了双向队列deque的数据结构类型,可以在队列的左端和右端实现入队和出队,在双向队列的右端指向入队和出队动作就可以模拟入栈和出栈。

from collections import deque

stack = deque()
#入栈
stack.append(1)
print(stack)
stack.append(2)
print(stack)
#出栈
a = stack.pop()
print(stack)
print(list(stack))

#判断栈是否为空
if list(stack):
    print('栈不为空!')
else:
    print('栈为空!')

二、队列的python实现

2.1、队列的列表实现

可以使用在列表尾部添加元素模拟入队,列表头部删除元素模拟出队。

queue = []
#入队
queue.append(1)
print(queue)
queue.append(2)
print(queue)
queue.append(5)
print(queue)
#出队
queue.pop(0)
print(queue)
#判断队列是否为空
if queue:
    print('Not Empty')
else:
    print('Empty')

2.2、使用deque实现队列

from collections import deque

queue = deque()
#入队
queue.append(1)
print(queue)
queue.append(1)
print(queue)
queue.append(7)
print(queue)
#出队
queue.popleft()
print(queue)
#在某位置插入元素
queue.insert(1,3)
print(queue)
#判断队列是否为空
if queue:
    print('Not Empty')
else:
    print('Empty')

三、堆的python实现

python中内置了实现堆的模块,可以直接调用。

import heapq

#列表h
h = [1,4,5,2,7]

#对h进行最小堆排序
heapq.heapify(h)
print(h)

#删除堆顶元素
a = heapq.heappop(h)
print('堆顶元素为:',a)
print('堆排序为:',h)
#在堆中加入一个元素val,并对堆重新排序
val = 3
heapq.heappush(h,val)
print('堆排序为:',h)

#在堆中加入一个元素,保持堆得元素数量不变,如果加入的元素大于堆顶元素则删除堆顶元素。
val = 4
heapq.heapreplace(h,val)
print('堆排序为:',h)
2019-06-14 00:27:15 cyl101816 阅读数 249
  • 数据结构基础系列(3):栈和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

一、概述

栈和队列是数组和链表的高级封装的数据结构。

栈和队列的重点在其结构特性,栈和队列的底层不论是数组实现还是链表实现都不重要,因为同属于线性存储结构,可以通过数组实现一个栈结构,也可以使用链表实现一个栈结构,同样队列也是如此。

二、实现

2.1 栈

2.1.1栈结构的特点

  • 栈的结构特性是:元素先进后出(First In Last Out,简称FILO)
  • 我们将元素放入栈结构中的操作称之为元素入栈
  • 将元素从栈结构中取出的操作称之为元素出栈
  • 将最先进入栈结构中的元素称之为栈底元素,这个方向同时称之为栈底
  • 将最后进入栈结构中的元素称之为栈顶元素,这个方法同时称之为栈顶

2.1.2 Java中的栈结构:Stack

在Java中存在一个栈结构的实现类,这个类是Stack类;
Stack类是Vector类的子类,从集成的角度来说,Stack类是List接口的实现类,同样属于Collection接口的实现类之一;
从这个角度来说,Stack类同样具有List接口下其他实现类类似的功能,能够有序可重复的保存元素;
但是除了这些特性之外,Stack类还提供了一些额外的方法,能够从数据结构的角度体现出栈结构的特性。

2.1.3 案例

1、.数组逆序

import java.util.Arrays;
import java.util.Stack;

public class ArrayReverseByStack {
	
	/**
	 * 使用栈结构实现数组元素逆序
	 * @param array 参数数组
	 */
	public void reverse(int[] array) {
		
		//[1]创建一个栈结构,用来逆序数组中的元素
		Stack<Integer> reverseStack = new Stack<>();
		
		//[2]将数组中全部元素入栈
		for(int i = 0; i < array.length; i++) {
			reverseStack.push(array[i]);
		}
		
		//[3]将栈结构中的所有元素出栈,出栈过程就是讲数组中元素逆序的过程
		for(int i = 0; i < array.length; i++) {
			array[i] = reverseStack.pop();
		}
		
	}
	
	public static void main(String[] args) {
		
		int[] array = new int[] {1,3,5,7,9};
		
		ArrayReverseByStack arbs = new ArrayReverseByStack();
		arbs.reverse(array);
		
		System.out.println(Arrays.toString(array));
		
	}
	
}

2、.10进制正整数转2进制

import java.util.Stack;

public class DecimalToBinary {
	
	/**
	 * 将一个10进制正整数转换为一个2进制字符串并返回
	 * @param num 作为参数的10进制整数
	 * @return 10进制整数对应的2进制字符串
	 */
	public String toBinary(int num) {
		
		//[1]创建一个栈结构,用来存储整除法产生的余数
		Stack<Integer> binaryStack = new Stack<>();
		
		//[2]对参数num进行对2的整除法,直到这个数取值为0为止,将过程中产生的所有余数全部入栈(最后产生的0不用入栈)
		int remainder = 0;  //创建一个临时变量,用来保存num对2的余数
		while(num > 0) {
			remainder = num % 2;
			binaryStack.push(remainder);  //余数入栈
			num /= 2;  //别忘了对num除以2,因为上面的步骤只是取余,没有除以2的功能
		}
		
		//[3]将栈中所有余数出栈,出栈过程就是倒排余数的过程
		String result = "0B";
		while(!binaryStack.isEmpty()) {  //只要栈结构不是空,就继续元素出栈
			result += binaryStack.pop();
		}
	
		//[4]返回结果值
		return result;
		
	}

	public static void main(String[] args) {
		
		int num = 12;  //12的2进制结构:0b1100
		
		DecimalToBinary dtb = new DecimalToBinary();
		String result = dtb.toBinary(num);
		System.out.println(result);
		
	}
	
}

2.2 队列

2.2.1 队列的结构特性

  • 队列的结构特性是:元素先进先出(First In First Out,简称FIFO)
  • 队列结构的特征就和现实生活中的排队买东西一样,先来排队的先买,一切先来后到,元素按照进入队列的顺序出队列
  • 我们将元素键入队列的操作,称之为元素入队列
  • 将元素从队列中取出的操作,称之为元素出队列
  • 将元素出队列的一端称之为队头(front)
  • 将元素入队列的一端称之为队尾(rear)

2.2.2 Java中的队列结构:LinkedLIst

  • Collection接口下,不仅仅有List和Set两大子接口,实际上还存在着一个名为Queue的接口,这个接口从名字上来看,本身就是队列的含义,并且这个接口还有一个子接口名为Deque(双端队列)
  • LinkedList类,一方面实现了List接口,一方面也实现了Deque接口,所以我们可以认为LinkedList本身就是一个通过链表实现的双端队列结构
  • 双端队列是一种两端可以同时元素入队列、出队列的结构,也就是说,两端同为队头和队尾

同样的,在LinkedList类型中,也提供了一些方法,用来支持队列操作:

2.2.3 案例

1、利用两个栈实现一个队列

给定元素加入结构顺序:a b c d e
元素出结构顺序:a b c d e
这个结构功能等同于一个队列结构,但是内部要求使用两个栈结构实现

import java.util.Stack;

/**
 * 使用两个栈结构模拟的队列
 */
public class StackQueue<E> {
	
	private Stack<E> s1 = new Stack<>();
	private Stack<E> s2 = new Stack<>();
	
	/**
	 * 将元素加入这个结构的方法
	 * @param e 加入结构的元素
	 */
	public void add(E e) {
		
		//[1]如果栈s2中还有剩余元素,说明上一次的出栈并没有“出干净”,还需要将s2中的元素全部入栈s1当中,保证元素加入结构的相对顺序不变
		if(!s2.isEmpty()) {
			while(!s2.isEmpty()) {
				E tmp = s2.pop();  //s2出栈
				s1.push(tmp);  //s1入栈
			}
		}
		
		//[2]如果元素要加入这个结构的话,那么首先将这些元素全部加入栈s1当中
		s1.push(e);
		
	}
	
	/**
	 * 将元素从结构中退出的方法
	 * @return 退出结构的元素
	 */
	public E get() {
		
		//[1]如果元素要从结构中退出,那么将栈s1中所有的元素全部出栈,并按照元素出栈顺序加入到栈s2中
		if(!s1.isEmpty()) {
			while(!s1.isEmpty()) {
				E tmp = s1.pop();  //s1出栈
				s2.push(tmp);  //s2入栈
			}
		}
		
		//[2]将栈s2中的栈顶元素出栈并返回,这个过程就是元素按照加入结构顺序退出的过程
		if(!s2.isEmpty()) {
			return s2.pop();
		}
		return null;
		
	}
	
	public static void main(String[] args) {
		
		StackQueue<Character> sq = new StackQueue<>();
		
		//加入结构5个元素
		sq.add('A');
		sq.add('B');
		sq.add('C');
		sq.add('D');
		sq.add('E');
		
		//退出结构3个元素
		System.out.println(sq.get());
		System.out.println(sq.get());
		System.out.println(sq.get());
		
		//再次加入结构3个元素
		sq.add('F');
		sq.add('G');
		sq.add('H');
		
		//全部元素退出结构
		System.out.println(sq.get());
		System.out.println(sq.get());
		System.out.println(sq.get());
		System.out.println(sq.get());
		System.out.println(sq.get());
		
	}
	
}

2、用两个队列实现一个栈

给定元素加入结构顺序:a b c d e
元素出结构顺序:e d c b a
这个结构功能等同于一个栈结构,但是内部要求使用两个队列结构实现

步骤(1):将全部加入结构的元素加入队列q1
步骤(2):当元素e要退出结构的时候,将q1中除了元素e之外的其他元素全部出队列q1,并同时加入队列q2
步骤(3):将队列q1中的元素e出队列,此时队列q1空
步骤(4):当元素d要退出结构的时候,将q2中除了元素d之外的其他元素全部出队列q2,并同时加入队列q1
步骤(5):将队列q2中的元素d出队列,此时队列q2空
……
以此类推,就能够实现元素的倒序输出

import java.util.LinkedList;

/**
 * 使用两个队列结构模拟的栈
 */
public class QueueStack<E> {

	private LinkedList<E> l1 = new LinkedList<>();
	private LinkedList<E> l2 = new LinkedList<>();
	
	private LinkedList<E> currentList = l1;  //创建一个队列变量,用来记录当前应该向哪一个队列中添加元素,默认初始情况是向l1中添加元素
	
	/**
	 * 元素加入结构的方法
	 * @param e 加入结构的元素
	 */
	public void add(E e) {
		
		//[1]向currentList中添加元素
		currentList.offer(e);
		
	}
	
	/**
	 * 元素退出结构的方法
	 * @return 退出结构的元素
	 */
	public E get() {
		
		//[1]将当前用来存储元素的队列中的n个元素的前n-1个元素出队列,并存储到另一个空队列中
		if(currentList == l1 && !l1.isEmpty()) {
			while(l1.size() > 1) {
				E tmp = l1.poll();  //l1出队列
				l2.offer(tmp);  //l2入队列
			}
			
			//[2]现在队列l1中仅剩一个元素,将这个元素出队列并返回,并且后来的元素全部存储在l2中
			currentList = l2;
			return l1.poll();
			
		}else if(currentList == l2 && !l2.isEmpty()) {
			while(l2.size() > 1) {
				E tmp = l2.poll();  //l2出队列
				l1.offer(tmp);  //l1如队列
			}
			
			//[2]现在队列l2中仅剩一个元素,将这个元素出队列并返回,并且后来的元素全部存储在l1中
			currentList = l1;
			return l2.poll();
			
		}else {  //如果两个队列中都没有任何元素,那么直接返回空,方法结束
			return null;
		}
		
	}
	
	public static void main(String[] args) {
		
		QueueStack<Character> qs = new QueueStack<>();
		
		//相结构中添加5个元素
		qs.add('A');
		qs.add('B');
		qs.add('C');
		qs.add('D');
		qs.add('E');
		
		//退出结构3个元素
		System.out.println(qs.get());
		System.out.println(qs.get());
		System.out.println(qs.get());
		
		//再次追加3个元素
		qs.add('F');
		qs.add('G');
		qs.add('H');
		
		//全部元素出结构
		System.out.println(qs.get());
		System.out.println(qs.get());
		System.out.println(qs.get());
		System.out.println(qs.get());
		System.out.println(qs.get());
		
	}
	
}

 

 

2018-07-08 15:50:36 weixin_42442713 阅读数 3555
  • 数据结构基础系列(3):栈和队列

    数据结构课程是计算机类专业的专业基础课程,在IT人才培养中,起着重要的作用。课程按照大学计算机类专业课程大纲的要求,安排教学内容,满足需要系统学习数据结构的人。系列课程包含11个部分,本课为第3部分栈和队列,介绍在系统软件和应用软件开发中大有用途的两种特殊线性表——栈和队列的构组成、存储结构的选择,以及基本运算的实现,通过相关的应用案例介绍了这些数据结构的应用方法。

    16803 人正在学习 去看看 贺利坚

一、 实验目的

1. 熟悉栈的特点(先进后出)及栈的抽象类定义;

2. 掌握栈的顺序存储结构和链式存储结构的实现;

3. 熟悉队列的特点(先进先出)及队列的抽象类定义;

4. 掌握栈的顺序存储结构和链式存储结构的实现;

二、实验要求

1. 复习课本中有关栈和队列的知识;

2. C++语言完成算法和程序设计并伤及调试通过;

三、实验题目与要求

1. 停车场问题——栈和队列的应用

【问题描述】设停车场是一个可停放 n 辆汽车的狭长通道,且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端)。若停车场内已经停满 n辆车,那么后来的车只能在门外的便道上等候。一旦有车开走,则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。

【基本要求】以栈模拟停车场,以队列模拟车场外的便道,按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据项:汽车的“到达”(‘A’表示)或“离去”(‘D’表示)信息、汽车标识(牌照号)以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或者便道上的停车位置;若是车辆离去,则输出汽车在停车场停留的时间和应缴纳的费用(便道上停留的时间不收费)。栈以顺序结构实现,队列以链表结构实现。

【输入输出】

① 初始,显示提示信息:“请输入停车场最大容量n=:”,提示用户输入停车场最大容量。

② 输入车辆信息:提示请输入车辆信息,提示用户输入车辆信息(“到达”或者“离开”,车牌编号,到达或者离开的时间),输入值的格式为:第一个必须为字母,后两个为数字,中间用逗号隔开。有以下几种情况:

③ 若车辆信息为“到达A”,车辆信息开始进栈(模拟停车场),当栈满,车辆会进队列(模拟停车场旁便道)。

④ 若车辆信息为“离开D”,会显示该车进入停车场的时间以及相应的停车费用,若该车较部分车早进停车场,这部分车需先退出停车场,暂时进入一个新栈为其让道,当待离开车离开停车场后,这部分车会重新进入停车场,同时便道上的第一辆车进入停车场。

⑤ 若输入(‘P’,0,0),会输出显示停车场的车数。

⑥ 若输入(‘W’,0,0),会输出显示便道上的车数。

⑦ 若输入(‘E’,0,0),程序会跳出循环,同时程序结束。

⑧ 用户每输入一组数据,程序就会根据相应输入给出输出。

【测试用例】

 

【算法分析】


【实现步骤】

(1) 步骤一:创建一头文件park.h,定义数据的结构及函数的声明

① 数据的表示

车辆信息的表示——表示汽车的状态(‘A’表示到达,‘D’表示离开)、车号、时间(到达或离开)

 

l 程序以顺序栈模拟停车场以及临时停放为给要离去的汽车让路而从停车场退出来的汽车的场地,以链表队列模拟车场外的便道,因此需要栈和队列这两个抽象数据类型。

 

上图为栈的结构定义,其中data数组存储栈元素信息,即车辆信息,top表示栈顶,MaxSize表示栈的最大容量。

 

上图为链队列结点的结构定义,其中data为结点的数据域,next为结点的指针域,以及链队列结构定义,包括队头指针front,及队尾指针rear,及队列元素总个数num。

② 数据的操作

声明以下函数

 

 

(2) 步骤二:创建文件park.cpp,实现park.h声明的函数

l 初始化栈

 

l 判断栈是否为空

 

 

l 其它函数请自行完成(可参考书P81P100

(3) 步骤三:创建文件main.cpp,完成主函数(在横线上补充合适的代码)

 

 

   


 


2. 表达式计算问题——栈的应用

利用栈将中缀表达式转成后缀表达式,并栈利用对转化后的后缀表达式求值(设计性实验),假设操作数均为整数。

           中缀表达式                      后缀表达式

            a*b+c                            ab*c+

            a+b*c                            abc*+

            a+(b*c+d)/e                     abc*d+e/+

例如计算后缀表达式4 3 5 * +   即计算 4+3*5

应输出结果 19

实现提示

中缀表达式转成后缀表达式算法思想:

1. 首先需要分配2个栈,一个作为临时存储运算符的栈S1(含一个结束符号),一个作为输入后缀表达式的栈S2(空栈),S1栈可先放入优先级最低的运算符#。

2. 从中缀表达式的左端开始取字符,逐序进行如下步骤:     

Ø 若取出的字符是数字,则分析出完整的操作数,将该操作数直接送入S2栈  

Ø 若取出的字符是运算符,则将该运算符与S1栈栈顶元素比较,如果该运算符优先级大于S1栈栈顶运算符优先级,则将该运算符进S1栈,否则,将S1栈的栈顶运算符弹出,送入S2栈中,直至S1栈栈顶运算符低于(不包括等于)该运算符优先级,则将该运算符送入S1栈。

Ø 若取出的字符是“(”,则直接送入S1栈栈顶。

Ø 若取出的字符是“)”,则将距离S1栈栈顶最近的“(”之间的运算符,逐个出栈,依次送入S2栈,此时抛弃“(”。

Ø 重复上面的1~4步,直至处理完所有的输入字符。

Ø 若取出的字符是'\0',则将S1栈内所有运算符(不包括“#”),逐个出栈,依次送入S2栈。     

完成以上步骤,S2栈便为后缀表达式输出结果,但需要对S2的内容进行逆序。因此,S2也可考虑用队列。

对已转化的后缀表达式求值步骤:

1. 若表达式输入未完毕,读入一个字符

2. 若是操作数,压入栈,转1

3. 若是运算符,从栈中弹出2个数,将运算结果再压入栈

4. 若表达式输入完毕,栈顶即所求表达式的值;

数与数之间采用空格进行分隔,若读到数字字符直到遇到空格,则将所有数字字符凑好形成操作数。

 下面附上完整代码:

头文件park.h


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#pragma warning(disable:4996)
using namespace std;
#define price 0.1 //车费 0.1元/分
typedef struct time{
	int hour;
	int min;
}Time;//时间结点

typedef struct node{
	char num[10];//车牌
	Time reach;//到达
	Time leave;//离去
}CarNode;//车辆信息结点

typedef struct{
	CarNode *elem;
	int top;  //top=-1为空栈
}SeqStackCar;   //顺序栈 模拟停车场

typedef struct car{
	CarNode data;   //数据域
	struct car *next;//指针域
}QueueNode;   //链队列结点

typedef struct{
	QueueNode *front;//头指针
	QueueNode *rear;//尾指针
}LinkQueue; //链队列  模拟停车便道

void InitStack(SeqStackCar *s,int n);//初始化停车场栈道
void In(SeqStackCar *s, CarNode x,int n);//进栈
void Out(SeqStackCar *s, CarNode *x);//出栈
void GetTop(SeqStackCar *s, CarNode *x);//获取栈顶

void InitQueue(LinkQueue *q);//初始化停车便道
void Enter(LinkQueue *q, CarNode x);//入队
void Delte(LinkQueue *q, CarNode *x);//出队

void Arrive(SeqStackCar *s, LinkQueue *q,int n);//车辆到达
void Leave(SeqStackCar *s, LinkQueue *p,int n);//车辆离开

void PrintfSeq(SeqStackCar *s);//打印停车场内车辆的信息
void PrintfQue(LinkQueue *q);//打印便道内车辆的信息

2. park.cpp(实现park.h声明的函数)

#include"park.h"
void InitStack(SeqStackCar *s,int n)
{
	s->elem = new CarNode[n];
	s->top = -1;
}
void In(SeqStackCar *s, CarNode x,int n)
{
	if (s->top == n- 1) return;
	s->top++;
	s->elem[s->top] = x;
}
void Out(SeqStackCar *s, CarNode *x)
{
	if (s->top == -1) return;
	else
	{
		*x = s->elem[s->top]; 
		s->top--;
	}
}
void GetTop(SeqStackCar *s, CarNode *x)
{
	if (s->top == -1) return;
	else *x = s->elem[s->top];
}
void InitQueue(LinkQueue *q)
{
	q->front = q->rear = (QueueNode *)malloc(sizeof(QueueNode));
	q->front->next = NULL;
}
void Enter(LinkQueue *q, CarNode x)
{
	QueueNode *newnode;
	newnode = (QueueNode *)malloc(sizeof(QueueNode));
	if (newnode != NULL)
	{
		newnode->data = x;
		newnode->next = NULL;
		q->rear->next = newnode;
		q->rear = newnode;
	}
	else return;
}
void Delte(LinkQueue *q, CarNode *x)
{
	QueueNode *s;
	if (q->front == q->rear) return;
	s = q->front->next;
	q->front->next = s->next;
	if (q->rear == s)
		q->rear = q->front;
	*x = s->data;
	free(s);
}
void Arrive(SeqStackCar *s, LinkQueue *q,int n)//s停车场,q便道
{
	CarNode p;
	if (s->top == n - 1)
	{ 
		printf("停车场已满,请将车停往免费便道等候!\n");
		printf("车正在进入免费便道,请录入车辆信息!\n");
		printf("车辆车牌:");
		scanf("%s", &p.num);
		Enter(q, p);
		printf("车辆已停入便道!\n");
	}
	else
	{
		printf("车正在进入停车场,请录入车辆信息!\n");
		printf("车辆车牌:");
		scanf("%s", &p.num);
		printf("进入的时间(x时x分):");
		scanf_s("%d %d", &p.reach.hour,&p.reach.min);
		printf("该车进入的时间为:%d:%d\n",p.reach.hour,p.reach.min);
		In(s, p,n);
		printf("该车辆停在车场的第%d位置上.\n", s->top+1);
	}
}
void Leave(SeqStackCar *s, LinkQueue *q,int n)
{
	CarNode p;
	SeqStackCar w;//临时栈,存放让路的车辆
	InitStack(&w,n);//初始化临时栈
	int i;
	double free;
	printf("离开车辆的车牌为:");
	scanf("%s", &p.num);
	for (i = 0; i <= s->top; i++)
	{
		if (strcmp(p.num,s->elem[i].num)==0)  //查找离开的车辆在停车场中的位置,返回i
		{
			printf("该车辆在停车场的第%d位置上.\n", i+1);
			printf("输入该车辆离开的时刻(x时x分):");
			scanf_s("%d %d", &s->elem[i].leave.hour, &s->elem[i].leave.min);
			printf("该车离开的时间为:%d:%d\n",s->elem[i].leave.hour, s->elem[i].leave.min);
			free = ((s->elem[i].leave.hour * 60 + s->elem[i].leave.min) - (s->elem[i].reach.hour * 60 + s->elem[i].reach.min))*price;
			printf("该车辆改收取的停车费用为%.2f元:\n", free);
			while (s->top != i)  //有车辆离开时,后面的车依次出栈,进入临时栈w,
			{
				CarNode x;
				Out(s, &x); //从模拟停车场出栈
				In(&w, x,n);//进入临时栈
			}
			s->top--;
			while (w.top > -1) //该车离开后,再让临时栈w停放的车进停车场栈s
			{
				CarNode y;   
				Out(&w, &y);
				In(s, y,n);
			}
			//有空位了,便道的第一辆车可进停车场
			if (q->front == q->rear)
				printf("便道内无停车,没车需进停车场!\n");
			else
			{
				CarNode c;
				Delte(q, &c);
				printf("车正在进入停车场,请录入车辆信息!\n");
				printf("车辆车牌:%s\n", c.num);
				printf("进入的时间(x时x分):");
				scanf_s("%d %d", &c.reach.hour, &c.reach.min);
				printf("该车进入的时间为:%d:%d\n",c.reach.hour, c.reach.min);
				In(s, c,n);
				printf("该车辆停在车场的第%d位置上.\n", s->top+1);
			}
		}
	}
}

void PrintfSeq(SeqStackCar *s)//打印停车场内车辆的信息
{
	if (s->top == -1)
		printf("停车场内为无停车!\n");
	else
	{
		printf("===============停车场内车辆信息如下===============\n");
		for (int i = 0; i <= s->top; i++)
		{
			printf("%d号车辆:车牌:%s\t进入时间:%d:%d\n", i+1, s->elem[i].num,s->elem[i].reach.hour,s->elem[i].reach.min);
		}
		printf("==================================================\n");
	}
}
void PrintfQue(LinkQueue *q)//打印免费便道内车辆的信息
{
	int i = 1;
	QueueNode *temp = q->front->next;
	if (q->front == q->rear)
		printf("免费便道内无停车!\n");
	else
	{
		printf("====免费便道内车辆信息如下====\n");
		while (temp!=NULL)
		{
			printf("\t%d号车辆:车牌:%s\n", i,temp->data.num);
			i++;
			temp = temp->next;
		}
		printf("==============================\n");
	}
}

3. main.cpp(程序入口)

#include"park.h"
void menu();//菜单
int main()
{
	int n;
	printf("请输入停车场的容量:");
	scanf("%d",&n);
	printf("停车能容纳%d辆车\n",n);
	system("pause");
	SeqStackCar S;
	LinkQueue Q;
	InitStack(&S,n);
	InitQueue(&Q);
	int userchoice;
	do{
		menu();
		scanf_s("%d", &userchoice);
		switch (userchoice)
		{
		case 0:break;
		case 1:Arrive(&S, &Q, n); break;
		case 2:Leave(&S, &Q, n); break;
		case 3:PrintfSeq(&S); break;
		case 4:PrintfQue(&Q); break;
		}
		system("pause");
	} while (userchoice != 0);
	return 0;
}
void menu()
{
	system("cls");
	printf("\t停车场系统\n\n\t0.退出\n\t1.车辆到达\n\t2.车辆离开\n\t3.打印停车场车辆信息\n\t4.打印便道车辆信息\n\n请输入你的选择:");
}

二、表达式计算问题
#include <iostream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
using namespace std;

const char oper[] = { ' ', '(', '+', '-', '*', '/', ')'};

bool isNum(char &ch) {
	if (ch >= '0' && ch <= '9') return true;
	return false;
}

int main(void) {
	map<char, int> mp; /*运算符与优先级的映射*/
	for (int i = 0; oper[i]; i++) {
		mp[oper[i]] = i;
	}
	char str[110];
	stack<char> ope; /*中缀转后缀暂存操作数栈*/
	queue<char> que; /*中缀转后缀暂存后缀表达式队列*/
	string PostFixExp;  /*保存后缀表达式*/
	stack<int> ss;   /*后缀表达式计算暂存操作数栈*/
	std::cout<<"输入算术表达式"<<endl;
	while (gets_s(str)) {
		for (int i = 0; str[i]; i++) {
			if (isNum(str[i])) {
				que.push(str[i]);/*如果是操作数是进队*/
			}
			else {
				que.push(' ');/*如果是操作符则先将空格进队,目的是用空格隔开操作数*/
				if (str[i] == '(') {
					ope.push(str[i]);/*左括号直接进队*/
					continue;
				}
				if (str[i] == ')') {
					while (ope.top() != '(') {
						que.push(ope.top());
						ope.pop();
					}
					ope.pop();
					continue;
				}
				while (!ope.empty() && ope.top() != '(' && mp[str[i]] <= mp[ope.top()]) {
					que.push(ope.top());
					ope.pop();
					
				}
				ope.push(str[i]);
			}
		}
		while (!ope.empty()) {
			que.push(ope.top());
			ope.pop();
		}
		while (!que.empty()) {
			if (isNum(que.front())) {
				int num = 0;
				while (isNum(que.front())) {
					num = num * 10 + que.front() - '0';
					PostFixExp+=que.front();
					que.pop();
				}
				ss.push(num);
 			}
			else {
				PostFixExp+=que.front();
				if (que.front() == '+') {
					int num2 = ss.top(); ss.pop();
					int num1 = ss.top(); ss.pop();
					ss.push(num1 + num2);
				}
				else if (que.front() == '-') {
					int num2 = ss.top(); ss.pop();
					int num1 = ss.top(); ss.pop();
					ss.push(num1 - num2);
				}
				else if (que.front() == '*') {
					int num2 = ss.top(); ss.pop();
					int num1 = ss.top(); ss.pop();
					ss.push(num1 * num2);
				}
				else if (que.front() == '/') {
					int num2 = ss.top(); ss.pop();
					int num1 = ss.top(); ss.pop();
					ss.push(num1 / num2);
				}
				que.pop();
			}
		}
		cout<<"后缀表达式为"<<PostFixExp<<"=";
		cout  << ss.top() << endl;
	}
}

举例:

(12+133)*10-340

读完字符串,队列的情况

空格

1

2

空格

1

3

3

空格

+

空格

1

0

空格

*

3

4

0

-




 

没有更多推荐了,返回首页